
#ifndef _SORT_H_
#define _SORT_H_

template<class T>
bool isSorted(T *a, int n){
	for(int i = 0; i < n-1; i++)
		if( !(a[i] <= a[i+1]))
			return false;
	return true;
}

//tested it works
template <class T>
void InsertionSort (T *a, int n)
{
    int i, j = 0;
    T key;
    for (i = 1; i < n; j = i, i++) {
        key = a[i];
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

//mot tested but assumed to work
template <class T>
void BubbleSort(T *a,int n)
{
	int i, j;
	T tmp;
    for (i = n - 1; i >= 0; i--) {
        for (j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

//tested it works
template<class T>
void SelectionSort(T *a, int n) {
    int i, j, minIndex;
	T tmp;    
    for (i = 0; i < n - 1; i++) {
		minIndex = i;
        for (j = i + 1; j < n; j++)
			if (a[j] < a[minIndex])
				minIndex = j;
            if (minIndex != i) {
				tmp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = tmp;
			}
		}
}

//tested it works
template <class T>
void ShellSort(T *a,int n)
{
	int htab[22] = { 14057, 9371, 6247, 4177, 2777, 1861, 1237, 823, 557, 367,251,
		163, 109, 73, 37, 19, 11, 7, 5, 3, 1, 0 };

	int *h, i, j;
    T tmp;

    for (h = htab; *h; h++) {
        for (i = *h; i < n; i++) {
            tmp = a[i];
            for (j = i; j >= *h && a[j - *h] > tmp; j -= *h)
                a[j] = a[j - *h];
            a[j] = tmp;
        }
    }
}

//tested it works
template <class T>
void QuickSort(T *a, int left, int right)
{
	int i = left, j = right;
	T tmp;
	int pivot = a[(left + right) / 2];
 
      
      while (i <= j) {
            while (a[i] < pivot)
                  i++;
            while (a[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = a[i];
                  a[i] = a[j];
                  a[j] = tmp;
                  i++;
                  j--;
            }
      }
      if (left < j)
            QuickSort(a, left, j);
      if (i < right)
            QuickSort(a, i, right);
	
}

//tested it does not work
template<class T>
void StoogeSort(T *a, int n, int i = 0){
	if(a[n] < a[i])
	{
		T tmp = a[n];
		a[n] = a[i];
		a[i] = tmp;
	}
	if((n - i + 1) >= 3){
		int t = (n-i+3)/3;
		StoogeSort(a,n-t,i);
		StoogeSort(a,n,i+t);
		StoogeSort(a,n-t,i);
	}
}

//NO
template <class T>
void CombSort(T *a,int n)
{
	int gap = n;
	T tmp;
	bool swapped = false;
	while(gap > 1 || !swapped){
		swapped = false;
		if(gap > 1)
			gap = (int)(gap/1.3);
		int i  = 1;
		while((i + gap) < n){
			if(a[i] > a[i+i])
			{
				tmp = a[i];
				a[i] = a[i+1];
				a[i+1] = tmp;
			}
			i++;
		}
	}
}

//tested it works
template <class T>
void GnomeSort(T *a, int n){
	int i = 0;
	while(i < n)
		if(i == 0 || a[i-1] <= a[i]) i++;
		else{
			T tmp = a[i];
			a[i] = a[i-1];
			a[--i] = tmp;
		}
}

#endif